package sortieren;

import java.util.LinkedList;
import java.util.Random;

/**Dies ist der abstrakte Vorfahr aller Sortieralgorithmen, die ein Array von
 * Zahlen sortieren und dafür nur Methoden für die Abfrage (get) und
 * Vertauschung (swap) benötigen. Implementiert werden muss nur noch die
 * Methode <code>sort</code>. Diese darf aber nicht aufgerufen werden. Der
 * Aufruf erfolgt von einem weiteren Thread, der durch <code>start</code>
 * gestartet werden kann.
 * <p>
 * Während des Sortierens können Markierungen gesetzt werden, die dann von
 * den angemeldeten <code>Demonstrator</code>en angezeigt werden können.
 * Nachfahren dieser Klasse müssen selber definieren, wie viele verschiedene
 * Markierungsarten sie benötigen. Ob die Markierungen angezeigt werden, liegt
 * aber im Ermessen der <code>Demonstrator</code>en.
 * </p><p>
 * Diese Klasse ist auch ohne Verständnis von Threads möglich, wenn man einfach
 * alle Stellen ignoriert, die von Threads handeln.
 * </p>
 */
public abstract class GetSwapSorter{
  public static final Random zufall=new Random();

  public final String name;

  /**Die zu sortierenden Zahlen*/
  private int[] zahlen;

  /**Anzahl der Zugriffe*/
  private int anzget;

  /**Anzahl der Vertauschungen*/
  private int anzswap;

  /**Anzahl der möglichen Markierungstypen dieses Sortieralgorithmus.*/
  private final int marktypes;

  /**Liste derer, die von Zugriffen und Vertauschungen wissen wollen.*/
  private final LinkedList<Demonstrator> dems;

  /**Millisekunden, die vergehen nach get, swap und mark, falls die Methoden
   * ohne die entsprechenden Parameter aufgerufen werden.*/
  public volatile int gmillis, smillis, mmillis;

  /**Jede Instanz eines Sortieralgorithmus kann unabhängig die sort-Methode
   * ausführen.
   */
  private Thread thread;

  /**Erzeugt einen Sortieralgorithmus.
   * @param marktypes Anzahl der möglichen Markierungstypen dieses
   * Sortieralgorithmus. Ein Selectionsort etwa könnte anzeigen wollen, welche
   * Stelle er als nächste besetzt und welche er gerade untersucht. Er hätte
   * folglich 2 marktypes. (Der unmarkierte Zustand wird nicht mitgezählt.)
   * @param name der Name des Sortieralgorithmus. Wenn keiner angegeben wird,
   * wird der Klassenname verwendet.
   */
  public GetSwapSorter(int marktypes, String name){
    this.marktypes=marktypes;
    anzget=anzswap=0;
    zahlen=null;
    dems=new LinkedList<Demonstrator>();
    if(name!=null) this.name=name;
    else this.name=getClass().getName();
  }
  public GetSwapSorter(int marktypes){ this(marktypes, null); }

  /**Sortiert die Zahlenmenge aufsteigend. Diese Methode darf nicht direkt
   * aufgerufen werden. Stattdessen wird der Vorgang durch die Methode start
   * angestoßen.
   */
  protected abstract void sort();

  /**Gibt eine der Zahlen aus der Menge zurück und zählt dieses
   * Ereignis mit. Eine Verzögerung wird auch erzeugt.
   * @param i der Index in der Zahlenmenge.
   * @param millis zur Verlangsamung verstreichende Zeit in Millisekunden.
   * @return die Zahl an der betreffenden Stelle.
   */  
  public final int get(int i, int millis){
    anzget++;
    for(Demonstrator d: dems) d.getAction(this, i);
    checkAndSleep(millis);
    return zahlen[i];
  }
  public final int get(int i){ return get(i, gmillis); }

  /**Vertauscht zwei Zahlen aus der Zahlenmenge und zählt dieses
   * Ereignis mit. Eine Verzögerung wird auch erzeugt.
   * @param a Index der einen Zahl.
   * @param b Index der zweiten Zahl.
   * @param millis zur Verlangsamung verstreichende Zeit in Millisekunden nach
   * dem Vertauschen.
   */  
  public final void swap(int a, int b, int millis){
    int h=zahlen[a];
    zahlen[a]=zahlen[b];
    zahlen[b]=h;
    anzswap++;
    for(Demonstrator d: dems) d.swapAction(this, a, b);
    checkAndSleep(millis);
  }
  public final void swap(int a, int b){ swap(a, b, smillis); }

  /**Informiert alle angemeldeten <code>Demonstrator</code>en, dass es günstig
   * wäre, eine Position hervorzuheben.
   * @param pos die zu markierende Position.
   * @param type Art der Markierung mit Werten von 0 (unmarkiert) bis höchstens
   * dem bei Konstruktor übergebenen Höchstwert.
   * @param millis zur Verlangsamung verstreichende Zeit in Millisekunden nach
   * dem Markieren.
   */
  public final void mark(int pos, int type, int millis){
    for(Demonstrator d: dems) d.markAction(this, pos, type);
    checkAndSleep(millis);
  }
  public final void mark(int pos, int type){ mark(pos, type, mmillis); }

  /**Testet, ob der ausführende Thread genau der eine ist, der durch 'start'
   * angestoßen wurde und ob dieser weitermachen soll.
   * Wurde der durch 'start' gestartete Thread mit 'stop' zur Unterbrechung
   * freigegeben, wird er hier endgültig gestoppt. Diese Methode sollte also
   * nur dort aufgerufen werden, wo das Stoppen des Threads keinen Schaden
   * anrichten kann.
   * @throws IllegalStateException wenn der laufende Thread ein anderer ist.
   * Dies kann dann passieren, wenn versehentlich sort direkt aufgerufen wurde.
   */
  private void checkAndSleep(int millis) throws IllegalStateException{
    if(thread!=Thread.currentThread())
      throw new IllegalStateException("Nicht durch 'start' gestartet.");
    boolean interrupted=thread.isInterrupted();
    if(millis>0)
      try{Thread.sleep(millis);}
      catch(InterruptedException ex){interrupted=true;}
    if(interrupted){
      thread.stop();
      thread=null;
    }
  }

  /**Registriert einen Demonstrator. Dieser wird immer dann benachrichtigt, wenn
   * ein entsprechendes Ereignis auftritt.
   * @param d der zu registrierende.
   */
  public void addDemonstrator(Demonstrator d){ dems.add(d); }

  /**Meldet einen Demonstrator ab.
   * @param d der abzumeldende.
   */
  public void removeDemonstrator(Demonstrator d){ dems.remove(d); }

  /**Erzeugt eine Menge von Zahlen, die einem Demonstrator zur Verwaltung gegeben
   * werden können. Sobald sie der Demonstrator hat, darf die Menge nicht mehr
   * verändert werden.
   * @param von kleinster gewünschter Zahlenwert (einschließlich).
   * @param bis größter gewünschter Zahlenwert (ausschließlich).
   * @param anz Größe der Zahlenmenge.
   * @param doppel true, wenn Doppelungen erlaubt sind, false, wenn nicht. Wenn
   * <CODE>anz &le bis-von</CODE>, sind Doppelungen automatisch erlaubt.
   * @return die erzeugte Zahlenmenge.
   */
  public static int[] generate(int von, int bis, int anz, boolean doppel){
    int[] zahlen=new int[anz];
    int bereich=bis-von;
    if(anz>bereich) doppel=true;
    if(doppel) for(int i=0; i<anz; i++) zahlen[i]=von+zufall.nextInt(bereich);
    else for(int i=0; i<anz; i++) zahlen[i]=von+i;
    return zahlen;
  }

  /**Übenimmt die zu sortierende Zahlenmenge. Wird <CODE>null</CODE> übergeben,
   * stellt der Demonstrator eine Default-Zahlenmenge zur Verfügung.
   * @param zahlen ebendiese.
   */
  public final void setAll(int[] zahlen){
    if(thread!=null && thread.isAlive())
      throw new IllegalStateException("Sortierung ist schon im Gange.");
    this.zahlen=zahlen;
    anzget=anzswap=0;
    for(Demonstrator d: dems) d.initAction(this);
  }

  public final void start() throws IllegalStateException{
    if(thread!=null && thread.isAlive())
      throw new IllegalStateException("Sortierung ist schon im Gange.");
    thread=new Thread(){
      @Override
      public void run(){
        sort();
        ready();
      }
    };
    thread.start();
  }
  private void ready(){ for(Demonstrator d: dems) d.readyAction(this); }

  public final void stop(){
    if(thread==null || !thread.isAlive())
      throw new IllegalStateException("Es ist keine Sortierung im Gange.");
    thread.interrupt();
  }

  /**Mischt die Zahlenmenge, ohne die Werte zu verändern.*/  
  public final void mix(){
    if(thread!=null && thread.isAlive())
      throw new IllegalStateException("Mischen impossible; Sortierung ist im Gange.");
    for(int i=0, n=zahlen.length; i<n; i++){
      int j=zufall.nextInt(n);
      int h=zahlen[i];
      zahlen[i]=zahlen[j];
      zahlen[j]=h;
    }
    anzget=anzswap=0;
    for(Demonstrator d: dems) d.initAction(this);
  }

  /**Gibt die Anzahl der bisher getätigten Zugriffe in die Zahlenmenge
   * wieder.
   * @return ebendiese.
   */  
  public final int countedGets(){return anzget;}

  /**Gibt die Anzahl der bisher getätigten Vertauschungen wieder.
   * @return ebendiese.
   */  
  public final int countedSwaps(){return anzswap;}

  /**Gibt einen Wert der zu sortierenden Menge zurück, ohne den Zugriff zu zählen.
   * Diese Methode sollte natürlich nicht von der Methode sortiere aufgerufen
   * werden.
   * @param i der Index der angeforderten Zahl.
   * @return Kopie der Zahlen, 
   */
  public final int uncountedGet(int i){return zahlen[i];}

  /**Gibt zurück, ob die Zahlenmenge schon aufsteigend sortiert ist.
   * Diese Methode sollte natürlich nicht von der Methode sortiere aufgerufen
   * werden.
   * @return true genau dann, wenn die Zahlenwerte monoton steigen.
   */
  public final boolean uncountedCheck(){
    for(int i=zahlen.length-1; i>0;)
      if(zahlen[i]<zahlen[--i]) return false;
    return true;
  }

  /**Gibt die Anzahl der zu sortierenden Zahlen zurück
   * @return ebendiese.
   */
  public final int length(){ return zahlen.length; }

  /**Gibt die Anzahl der möglichen Markierungstypen an.
   * @return ebendiese.
   */
  public final int marktypes(){ return marktypes; }
}
